#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<iostream>
#include<string>

using namespace std;

class Solution1 {
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        if(strs.empty())
            return "";
        string tmp(strs[0].begin(),strs[0].end());
        for(int i=0;i<strs.size()-1;i++)
        {
            int j=0;
            while(j<strs[i].size()&&j<strs[i+1].size())
            {
                if(strs[i][j]==strs[i+1][j]&&j<=tmp.size())
                    j++;
                else
                {
                    break;
                }               
            }
            if(j<=tmp.size())
                tmp.resize(j);
        }
        return tmp;    
    }
};


class Solution2 {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        for (int L = 2; L <= n; L++) {
            for (int i = 0; i < n; i++) {
                int j = L + i - 1;
                if (j >= n) {
                    break;
                }
                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};



void test1()
{
    Solution1 SL;
    vector<string> strs{ "acc","aaa","aaba" };
    //cout<<SL.longestCommonPrefix({ "acc","aaa","aaba" });
    cout<<SL.longestCommonPrefix(strs)<<endl;
}


int main()
{
    test1();
    return 0;
}